// https://leetcode.cn/problems/maximum-length-of-pair-chain/

// 算法思路总结：
// 1. 按区间起点排序所有数对
// 2. 动态规划求解最长数对链长度
// 3. 检查每个区间是否能接在前面的区间后面
// 4. 时间复杂度：O(n²)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm> 

class Solution 
{
public:
    int findLongestChain(vector<vector<int>>& pairs) 
    {
        int m = pairs.size();
        if (m == 1) return 1;

        sort(pairs.begin(), pairs.end(), [](const vector<int>& x, const vector<int>& y){return x[0] < y[0];});

        vector<int> dp(m, 1);
        for (int i = 1 ; i < m ; i++)
        {
            for (int j = 0 ; j < i ; j++)
            {
                if (pairs[i][0] > pairs[j][1])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }     
        }

        int ret = 1;
        for (const int& num : dp)
            ret = max(ret, num);

        return ret;
    }
};

int main()
{
    vector<vector<int>> vv1 = {{1,2}, {2,3}, {3,4}};
    vector<vector<int>> vv2 = {{1,2}, {7,8}, {4,5}};

    Solution sol;

    cout << sol.findLongestChain(vv1) << endl;
    cout << sol.findLongestChain(vv2) << endl;

    return 0;
}